/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 迭代，DFS
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function(root) {
    let queue = [root],
    tempPathQueue = [`${root.val}`];

    while(queue.length>0){
        let node,tempPath,
        length = queue.length,
        emptyNode = 0;

        for(let i = 0;i<length;i++){
            node = queue.shift()
            tempPath = tempPathQueue.shift()
            if(node.left || node.right){
                node.left && tempPathQueue.push(tempPath + '->' + node.left.val) && queue.push(node.left)
                node.right && tempPathQueue.push(tempPath + '->' + node.right.val) && queue.push(node.right)
            }else{
                emptyNode++
                queue.push(node)
                tempPathQueue.push(tempPath)
            }
        }

        if(emptyNode === length){
            return tempPathQueue
        }
    }
};



/**
 * 递归，BFS
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function (root) {
    let allPath = []
    getAllPath(root, allPath,[])
    return allPath
};

function getAllPath(root, allPath,str) {
    if(root === null){
        return null
    }

    str.push(root.val)
    if(root.left === null && root.right === null){
        allPath.push(str.join("->"))
    }

    root.left && getAllPath(root.left,allPath,str)
    root.right && getAllPath(root.right,allPath,str)

    str.pop()
}


/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function (root) {
    let allPath = []
    getAllPath(root, allPath, "")
    return allPath
};

function getAllPath(root, allPath, str) {
    str += root.val
    if (root.left === null && root.right === null) {
        allPath.push(str)
        return
    }

    root.left && getAllPath(root.left, allPath, str + "->")
    root.right && getAllPath(root.right, allPath, str + "->")
}